Nếu mỗi nút và cạnh có thể được biểu diễn trong bộ nhớ Θ ( 1 ) {\displaystyle \Theta (1)} , thì có thể lưu trữ cả cây trong bộ nhớ Θ ( n ) {\displaystyle \Theta (n)} . Tổng độ dài các xâu trên các cạnh của cây là O ( n 2 ) {\displaystyle O(n^{2})} , nhưng có thể lưu mỗi cạnh bằng vị trí bắt đầu và kết thúc của một xâu con của S, nên tổng bộ nhớ cần dùng là Θ ( n ) {\displaystyle \Theta (n)} . Trường hợp xấu nhất của bộ nhớ cần dùng cho cây hậu tố là khi dữ liệu vào là một từ fibonacci, đòi hỏi 2 n {\displaystyle 2n} nút.

Một lựa chọn quan trọng khi lập trình cây hậu tố là biểu diễn liên kết giữa nút cha và con trong cây. Cách đơn giản nhất là sử dụng danh sách liên kết gọi là danh sách chị em. Mỗi nút có một con trỏ trỏ tới nút con đầu tiên, và một con trỏ thứ hai trỏ tới nút kế tiếp trong danh sách chị em của nút đó. Cũng có thể sử dụng bảng băm, mảng đã sắp hoặc chưa sắp (sử dụng kĩ thuật gấp đôi mảng), hoặc cây nhị phân cân bằng. Mỗi lựa chọn cho một thời gian chạy khác nhau. Ta quan tâm tới:

• Chi phí tìm cạnh tới nút con có nhãn bắt đầu bằng một ký tự cho trước.
• Chi phí chèn thêm một nút con.
• Chi phí duyệt tất cả các nút con (chia trung bình cho mỗi nút con).

Đặt σ {\displaystyle \sigma } là kích thước bảng chữ cái. Khi đó các chi phí là như sau:

Ghi chú là chi phí chèn là chi phí trừ dần (do gấp đôi mảng) và chi phí của bảng băm là khi sử dụng băm hoàn hảo.

Lượng thông tin cần lưu cho mỗi cạnh và nút của cây hậu tố là rất tốn kém, tiêu tốn khoảng 10 đến 20 lần lượng bộ nhớ cần thiết để lưu xâu ký tự ban đầu. Mảng hậu tố giảm tỉ lệ này xuống còn 4 và các nhà nghiên cứu vẫn đang tìm cấu trúc dữ liệu mới để giảm tỉ lệ này xuống nhỏ hơn nữa.